#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#include<windows.h>

//5.1 结构体设计
//5.1.1 地图表示与存储结构体设计
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20                         //城市名称的长度
#define CITYNUM 5
#define ArcNum (CITYNUM-1)*CITYNUM/2
typedef char CITYNAME[MAXSIZE];
typedef struct ARCTYPE
{
    CITYNAME v,u;
    float distance;
}ARCTYPE,*MAPGRAPH;
MAPGRAPH map;
typedef int STATUS;

//5.1.2 旅行商路径表示与存储结构设计
typedef struct TRAVELPATH
{
    CITYNAME city[CITYNUM+1];
    float globaldistance;
}TRAVELPATH;
/*
TRAVELPATH trapath={{"A","D","E","C","B","A"},24};
TRAVELPATH trapathres;
*/
//5.2 递推的旅行商最优路径寻找
//5.2.1 两个城市之间的距离
float dist(MAPGRAPH map,CITYNAME u,CITYNAME v)
{
    float dis=0;
    int i;
    for(int i=0;i<ArcNum;i++)
    {
        if((strcmp(map[i].u,u)==0&&strcmp(map[i].v,v)==0)||
           (strcmp(map[i].u,v)==0&&strcmp(map[i].v,u)==0))
        {
            dis=map[i].distance;
            break;
        }
    }
    return dis;
}

//5.2.2 计算旅行商路径总长度
void TraPathDis(MAPGRAPH map,TRAVELPATH *trapath)
{
    float dis=0;
    int i;
    for(i=0;i<CITYNUM;i++)
    {
        dis+=dist(map,trapath->city[i],trapath->city[i+1]);
    }
    trapath->globaldistance=dis;
}

//5.2.3 复制旅行商路径
void CopyTraPath(TRAVELPATH *trapath,TRAVELPATH *newtrapath)
{
    int i;
    for(i=0;i<CITYNUM+1;i++)
    {
        strcpy(newtrapath->city[i],trapath->city[i]);
    }
}

//5.2.4 交换旅行商路径中两个城市进而形成新的路径
void ExchangeCityForPath(TRAVELPATH *trapath,int loci,int locj)
//在旅行商路径中交换两个城市进而形成新的路径
{
    CITYNAME temp;
    strcpy(temp,trapath->city[loci]);                 //交换两个城市名
    strcpy(trapath->city[loci],trapath->city[locj]);
    strcpy(trapath->city[locj],temp);
}

//5.2.5 定义当前可派生出路径数
#define NEIGHBORNUM ((CITYNUM-1)-1) * (CITYNUM-1) /2

//5.2.6 当前旅行商路径派生其近邻的所有路径
TRAVELPATH *ExpandTraPaths(MAPGRAPH map,TRAVELPATH *trapath)
//给定路径并派生其邻近的所有路径
{
    CITYNAME *trapath1,temp; 
    int i,loci,locj;             //循环控制变量，城市位置变量
    TRAVELPATH *neighbors;       //派生所有最近邻路径
    neighbors=(TRAVELPATH *)malloc(sizeof(TRAVELPATH)*NEIGHBORNUM);   //分配足够存储派生旅行商路径的连续存储单元
    for(i=0;i<NEIGHBORNUM;i++)                 //复制路径
    {
        CopyTraPath(trapath,&neighbors[i]);    //复制NEIGHBORNUM次当前路径
    }
    for(i=0,loci=1;loci<CITYNUM-1;loci++)      //所有交换位置
    {
        for(locj=loci+1;locj<CITYNUM;locj++)   //交换所有可能路径中的两个城市，生成派生路径
        {
            ExchangeCityForPath(&neighbors[i],loci,locj);  //交换loci与locj两个城市
            TraPathDis(map,&neighbors[i]);                 //派生路径的长度
            i++;                                           //旅行商的下一条路径
        }
    }
    return neighbors;                                      //所有派生路径
}

//5.2.7 清除所有旅行商路径
void ClearAllTraPaths(TRAVELPATH *neighbors)
{
    free(neighbors);
}

//5.2.8 旅行商路径初始化
void InitTraPath(MAPGRAPH map,CITYNAME cities[CITYNUM],CITYNAME start,TRAVELPATH *trapath)
//给定出发城市，随机产生旅行商路径
{
    int i,j=0,k,n;
    CITYNAME cs[CITYNUM-1],temp;            //除出发城市以外的所有城市
    for(i=0;i<CITYNUM;i++)                  //所有城市
    {
        if(strcmp(cities[i],start)!=0)      //去除出发城市（也是终点城市）
        {
            strcpy(cs[j++],cities[i]);      //保留除出发城市之外的所有城市
        }
    }
    strcpy(trapath->city[0],start);         //旅行商的出发城市
    strcpy(trapath->city[CITYNUM],start);   //旅行商的终点城市
    srand((unsigned)time(NULL));            //当前计算机时间为随机种子
    n=rand()%(CITYNUM-1);                   //0~CITYNUM-2随机数构成循环次数
    for(i=0;i<n;i++)                        //随机循环CITYNUM-1次
    {                                       //形成旅行商随机路径，即搜索空间的随机节点
        j=rand()%(CITYNUM-1);               //随机数的下标为0~CITYNUM-2
        k=rand()%(CITYNUM-1);               //随机数的下标为0~CITYNUM-2
        if(j==k)  continue;                 //下标相同，无须交换
        strcpy(temp,cs[j]);                 //下标不同，交换城市
        strcpy(cs[j],cs[k]);
        strcpy(cs[k],temp);
    }
    for(i=1;i<CITYNUM;i++)                  //形成旅行商随机路径，即搜索空间的随机节点
    {
        strcpy(trapath->city[i],cs[i-1]);   //放回旅行商路径中
    }
    TraPathDis(map,trapath);                //旅行商路径的总长度
}

//5.2.9 旅行商最短路径求解
void SearchResult(MAPGRAPH map,TRAVELPATH *trapath,TRAVELPATH *trapathres)
//给定地图和初始旅行商路径，求解旅行商最短路径，即在搜索空间中搜索最短路径
{
    TRAVELPATH *neighbors;          //所有派生的旅行商路径
    STATUS flag=FALSE;              //默认当前最小
    int i;
    CopyTraPath(trapath,trapathres);//复制旅行商初始路径
    TraPathDis(map,trapathres);     //计算路径的总长度
    while(TRUE)                     //无限搜索
    {
        neighbors=ExpandTraPaths(map,trapathres);                        //产生旅行商所有邻近路径集合
        for(i=0;i<NEIGHBORNUM;i++)                                       //逐一比较判断旅行商路径
        {
            if(trapathres->globaldistance>neighbors[i].globaldistance)
            //当前旅行商路径的长度比某个邻近路径的长度长，但不一定是最长的
            {
                flag=TRUE;                                //找到邻近更短的旅行商路径
                CopyTraPath(&neighbors[i],trapathres);    //更新更短的旅行商路径
                TraPathDis(map,trapathres);               //更新更短旅行商路径的长度
                break;
            }
        }
        if(flag==TRUE)                                   //邻近更短的旅行商路径
        {
            flag=FALSE;                                  //再次查找
        }
        else                                             //当前的旅行商路径是最短的
        {
            break;                                       //无须再搜索求解
        }
        ClearAllTraPaths(neighbors);                     //清除所有邻近旅行商路径
    }
}

//5.2.10 显示旅行商路径
void PriTraPath(TRAVELPATH path)
{
    int count=0;
    while(1)
    {
        if(count!=CITYNUM)       printf("%s->",path.city[count]);
        else if (count==CITYNUM) 
        {
            printf("%s",path.city[count]);
            break;
        }
        count++;
    }
    printf("\nGlobal Distance=%.2f\n",path.globaldistance);
}


//5.2.M 主程序
void main()
{
    int i;
    TRAVELPATH trapath,trapathres;                       
    CITYNAME cities[CITYNUM]={"A","B","C","D","E"};      //城市集合
    ARCTYPE map[ArcNum]={{"A","B",3},{"A","C",2},{"A","D",9},{"A","E",7},{"B","C",7},
                         {"B","D",2},{"B","E",5},{"C","D",9},{"C","E",2},{"D","E",3}};//城市地图
    for(i=0;i<10;i++)                              //求解2次最短旅行商路径
    {
        InitTraPath(map,cities,"A",&trapath);      //初始化旅行商路径
        printf("Init Path:");                      //显示旅行商路径
        PriTraPath(trapath);
        SearchResult(map,&trapath,&trapathres);    //最短旅行商路径
        printf("Result Path:");                    //显示旅行商路径
        PriTraPath(trapathres);
        printf("===============================\n");
        Sleep(6000);
    }
}